\documentclass[10pt]{sigplanconf}
%\documentclass{sigplanconf}

\usepackage{amssymb}
\usepackage{amsthm}
\usepackage{breakurl}             % Not needed if you use pdflatex only.
\usepackage{color}
\usepackage{epsfig}
\usepackage{esvect}
\usepackage{listings}
\usepackage{mathpartir}
\usepackage{MnSymbol}
\usepackage{multirow}
\usepackage{rotating}

\newtheorem{definition}{Definition}
\newtheorem{theorem}{Theorem}
\newtheorem{lemma}{Lemma}
\newtheorem{proposition}{Proposition}
\newtheorem{corollary}{Corollary}

\DeclareMathOperator*{\argmin}{arg\,min}
\DeclareRobustCommand{\Cpp}{C\texttt{++}}
\DeclareRobustCommand{\code}[1]{{\lstinline[breaklines=false,escapechar=@]{#1}}}
\DeclareRobustCommand{\codebr}[1]{{\lstinline[breaklines=true]{#1}}}
\DeclareRobustCommand{\codehaskell}[1]{{\lstinline[breaklines=false,language=Haskell]{#1}}}
\DeclareRobustCommand{\codeocaml}[1]{{\lstinline[breaklines=false,language=Caml]{#1}}}
\DeclareRobustCommand{\concept}[1]{{\small\textsc{#1}}}

\newcommand{\exclude}[1]{}
\newcommand{\halfline}{\vspace{-1.5ex}}
\newcommand{\textoverline}[1]{$\overline{\mbox{#1}}$}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

% listings settings

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\lstdefinestyle{C++}{language=C++,%
showstringspaces=false,
  columns=fullflexible,
  escapechar=@,
  basicstyle=\sffamily,
%  commentstyle=\rmfamily\itshape,
  moredelim=**[is][\color{white}]{~}{~},
  morekeywords={concept,decltype,noexcept,nullptr,requires},
  literate={[<]}{{\textless}}1      {[>]}{{\textgreater}}1 %
           {*}{{$*$}}1 % Without this, star (*) is rendered in Type 3 font
           {<}{{$\langle$}}1        {>}{{$\rangle$}}1 %
           {<=}{{$\leq$}}1          {>=}{{$\geq$}}1 %
           {==}{{$==$}}2            {!=}{{$\neq$}}1 %
           {=>}{{$\Rightarrow\;$}}1 {->}{{$\rightarrow{}$}}1 %
           {<:}{{$\subtype{}\ $}}1  {<-}{{$\leftarrow$}}1 %
           {s1;}{{$s_1$;}}3 {s2;}{{$s_2$;}}3 {s3;}{{$s_3$;}}3 {s4;}{{$s_4$;}}3 {s5;}{{$s_5$;}}3 {s6;}{{$s_6$;}}3 {s7;}{{$s_7$;}}3 {sn;}{{$s_n$;}}3 {si;}{{$s_i$;}}3%
           {P1}{{$P_1$}}2 {P2}{{$P_2$}}2 {P3}{{$P_3$}}2 {P4}{{$P_4$}}2 {P5}{{$P_5$}}2 {P6}{{$P_6$}}2 {P7}{{$P_7$}}2 {Pn}{{$P_n$}}2 {Pi}{{$P_i$}}2%
           {D1}{{$D_1$}}2 {D2}{{$D_2$}}2 {D3}{{$D_3$}}2 {D4}{{$D_4$}}2 {D5}{{$D_5$}}2 {D6}{{$D_6$}}2 {D7}{{$D_7$}}2 {Dn}{{$D_n$}}2 {Di}{{$D_i$}}2%
           {T1}{{$T_1$}}2 {T2}{{$T_2$}}2 {T3}{{$T_3$}}2 {T4}{{$T_4$}}2 {T5}{{$T_5$}}2 {T6}{{$T_6$}}2 {T7}{{$T_7$}}2 {Tn}{{$T_n$}}2 {Ti}{{$T_i$}}2 {Tm}{{$T_m$}}2%
           {e1}{{$e_1$}}2 {e2}{{$e_2$}}2 {e3}{{$e_3$}}2 {e4}{{$e_4$}}2%
           {E1}{{$E_1$}}2 {E2}{{$E_2$}}2 {E3}{{$E_3$}}2 {E4}{{$E_4$}}2 {Ei}{{$E_i$}}2%
           {m_e1}{{$m\_e_1$}}4 {m_e2}{{$m\_e_2$}}4 {m_e3}{{$m\_e_3$}}4 {m_e4}{{$m\_e_4$}}4%
           {Divide}{{Divide}}6 {Either}{Either}6 %
           {Times}{{Times}}5 %
           {Match}{{\emph{Match}}}5 %
           {Case}{{\emph{Case}}}4 %
           {Qua}{{\emph{Qua}}}3 %
           {When}{{\emph{When}}}4 %
           {Otherwise}{{\emph{Otherwise}}}9 %
           {EndMatch}{{\emph{EndMatch}}}8 %
           {CM}{{\emph{CM}}}2 {KS}{{\emph{KS}}}2 {KV}{{\emph{KV}}}2 %
           {EuclideanDomain}{\concept{EuclideanDomain}}{15}  %
           {LazyExpression}{\concept{LazyExpression}}{14}    %
           {Polymorphic}{\concept{Polymorphic}}{11}          %
           {Convertible}{\concept{Convertible}}{11}          %
           {Integral}{\concept{Integral}}8                   %
           {SameType}{\concept{SameType}}8                   %
           {Pattern}{\concept{Pattern}}7                     %
           {Regular}{\concept{Regular}}7                     %
           {Object}{\concept{Object}}6                       %
           {Field}{\concept{Field}}5                         %
}
\lstset{style=C++}

\lstdefinestyle{Haskell}{language=Haskell,%
  morekeywords={out,view,real}
  literate={=>}{{$\Rightarrow\;$}}1 {->}{{$\rightarrow{}$}}1 {<-}{{$\leftarrow$}}1 {\\}{{$\lambda$}}1,
  moredelim=**[is][\color{red}]{`}{`},
  moredelim=**[is][\color{white}]{~}{~}
}

\lstdefinestyle{GJ}{language=Java,
  moredelim=**[is][\color{red}]{`}{`},
  moredelim=**[is][\color{white}]{~}{~}
}
\lstdefinestyle{Eiffel}{language=Eiffel,%
  literate={->}{{$\rightarrow$}}1,
  moredelim=**[is][\color{red}]{`}{`},
  moredelim=**[is][\color{white}]{~}{~}
}
\lstdefinestyle{Csharp}{language=[Sharp]C,
  morekeywords={where,require,type},
  literate={->}{{$\rightarrow{}$}}1,
  moredelim=**[is][\color{red}]{`}{`},
  moredelim=**[is][\color{white}]{~}{~}
}

\lstdefinestyle{ML}{language=ML,%
  literate={->}{{$\rightarrow{}$}}1,
  moredelim=**[is][\color{red}]{`}{`},
  moredelim=**[is][\color{white}]{~}{~}
}

\lstdefinestyle{Caml}{language=Caml,%
  morekeywords={when}
  literate={->}{{$\rightarrow{}$}}1,
  moredelim=**[is][\color{red}]{`}{`},
  moredelim=**[is][\color{white}]{~}{~}
}

%% grammar commands
\newcommand{\Rule}[1]{{\rmfamily\itshape{#1}}}
\newcommand{\Alt}{\ensuremath{\mid}}
\newcommand{\SynCat}[1]{\ensuremath{\mathit{#1}}}
\newcommand{\is}{\ensuremath{::=}}
\newcommand{\subtype}{\ensuremath{\texttt{\raisebox{-0.1ex}{<}\raisebox{0.05ex}{:}}}}
\newcommand{\subtypeD}{\ensuremath{<:_d}}
\newcommand{\lazyevals}{\Downarrow}
\newcommand{\evals}{\Rightarrow}
\newcommand{\evalspp}{\Rightarrow^+}
\newcommand{\DynCast}[2]{\ensuremath{\mathsf{dyn\_cast}\langle{#1}\rangle({#2})}}
\newcommand{\nullptr}{\ensuremath{\bot}}
\newcommand{\of}[1]{\left(#1\right)}

\newcommand{\f}[1]{{{{#1\%}}}}
\newcommand{\s}[1]{{{\bf \underline{#1\%}}}}
\newcommand{\n}[1]{{{\bf ~ ~ ~ ~ }}}
\newcommand{\Opn}{{\scriptsize {\bf Open}}}
\newcommand{\Cls}{{\scriptsize {\bf Tag}}}
\newcommand{\Unn}{{\scriptsize {\bf Union}}}
\newcommand{\xV}{\tiny{x86-32}}
\newcommand{\xW}{\tiny{x86-64}}

\input{data3}

\newsavebox{\sembox}
\newlength{\semwidth}
\newlength{\boxwidth}

\newcommand{\Sem}[1]{%
\sbox{\sembox}{\ensuremath{#1}}%
\settowidth{\semwidth}{\usebox{\sembox}}%
\sbox{\sembox}{\ensuremath{\left[\usebox{\sembox}\right]}}%
\settowidth{\boxwidth}{\usebox{\sembox}}%
\addtolength{\boxwidth}{-\semwidth}%
\left[\hspace{-0.3\boxwidth}%
\usebox{\sembox}%
\hspace{-0.3\boxwidth}\right]%
}

\newcommand{\authormodification}[2]{{\color{#1}#2}}
\newcommand{\ys}[1]{\authormodification{blue}{#1}}
\newcommand{\bs}[1]{\authormodification{red}{#1}}
\newcommand{\gdr}[1]{\authormodification{magenta}{#1}}

\begin{document}

\conferenceinfo{ISO/IEC IS 14882:2003} {Programming Language C++}
\CopyrightYear{2012}
\copyrightdata{PL22.16/12-0139 = WG21 N3449}

\titlebanner{Draft for OOPSLA 2012} % These are ignored unless
\preprintfooter{Y.Solodkyy, G.Dos Reis, B.Stroustrup: Open and Efficient Type Switch for \Cpp{}}   % 'preprint' option specified.

\title{Open and Efficient Type Switch for \Cpp{}}
%\subtitle{your \code{visit}, Jim, is not \code{accept}able anymore}
%\subtitle{\code{accepting} aint no \code{visit}ors}

\authorinfo{Yuriy Solodkyy\and Gabriel Dos Reis\and Bjarne Stroustrup}
           {Texas A\&M University\\ Texas, USA}
           {\{yuriys,gdr,bs\}@cse.tamu.edu}

\maketitle

\begin{abstract}
%Selecting operations based on a type of an object determined at run-time is key 
%to many object-oriented and functional programming techniques. We present 
%techniques that can implement efficient type switching, type testing, pattern 
%matching, predicate dispatch, multi-methods in a compiler or a library. The 
%techniques are general and cope well with \Cpp{} multiple inheritance.
%
%Our library-only implementation provides a functional programming style notation 
%to the programmer. It outperforms the visitor design pattern, as commonly used 
%for type-casing scenarios in \Cpp{}. For many use cases it equals or outperforms 
%equivalent code in languages with built-in type switching constructs, such as 
%OCaml. We find the pattern-based library code easier to read and write and more 
%expressive than hand-coded visitors. The library is non-intrusive and does not have 
%extensibility restrictions. It also avoids control inversion characteristic to 
%visitors.
% 
%The library was motivated by and is used for applications involving large, 
%typed, abstract syntax trees. Being a library only solution allows us to use 
%production quality compilers and tool chains for our experiments and our 
%intended applications.

Selecting operations based on the run-time type of an object is key to many
object-oriented and functional programming techniques. We present a technique
for implementing open and efficient type switching on hierarchical extensible 
data types. The technique is general and copes well with \Cpp{} multiple 
inheritance.
 
To simplify experimentation and gain realistic performance using production-quality
compilers and tool chains, we implement a type switch construct as an ISO \Cpp{}11 
library, called \emph{Mach7}\footnote{The library is available at http://parasol.tamu.edu/mach7/}. 
This library-only implementation provides concise notation and
outperforms the visitor design pattern, commonly used for case analysis on types 
in object-oriented programming. For closed sets of types, its performance roughly equals equivalent code in 
functional languages, such as OCaml and Haskell. The type-switching code is easier to use and is more expressive  
than hand-coded visitors are. The library is non-intrusive and circumvents most of
the extensibility restrictions typical of the visitor design pattern. 
It was motivated by applications involving large, typed, abstract
syntax trees. 

%We present techniques that can be used in a compiler or library setting to 
%efficiently implement type switching, type testing, pattern matching, predicate 
%dispatch, multi-methods and other facilities that depend on the run-time type 
%of an argument. The techniques cope well with multiple inheritance in \Cpp{}, 
%however they are not specific to \Cpp{} and can be adapted to implement 
%similar facilities in other languages.
%
%Our library-only implementation of a type switch based on these techniques equals 
%or outperforms the visitor design pattern, as commonly used for type-casing 
%scenarios in \Cpp{}. For many use cases, it equals or outperforms equivalent 
%code in languages with built-in type-switching constructs. While remaining a 
%library-only solution, such a facility better addresses the expression problem 
%than the visitor design pattern does: it is non-intrusive and does not have 
%extensibility restrictions. It also avoids the control inversion characteristic to 
%visitors, thereby making the code significantly more concise and easier to comprehend.
%The library was motivated by and is used for applications involving large, 
%typed abstract syntax trees.
\end{abstract}

\category{D.1.5}{Programming techniques}{Object-oriented Programming}
\category{D.3.3}{Programming Languages}{Language Constructs and Features} 

\terms
Languages, Design

\keywords
Type Switch, Typecase, Visitor Design Pattern, Memoization, \Cpp{}

\input{sec-introduction}
\input{sec-problem}
\input{sec-memoization}
%\input{sec-exceptions}
%\input{sec-memcast}
\input{sec-evaluation}
\input{sec-related}
\input{sec-conclusions}
\input{sec-future}

\acks

We would like to thank Xavier Leroy and Luc Maranget for valuable feedback, and 
suggestions for improvements on the initial idea; Gregory Berkolaiko and 
Suhasini Subba Rao for ideas related to minimization of conflicts; Jaakko 
J\"arvi for assistance in comparison to other languages; and, Peter Pirkelbauer, 
Andrew Sutton, and Abe Skolnik for useful discussions that helped shape this 
work. We also benefitted greatly from the insightful comments by our anonymous 
reviewers. Finally, we would like to thank Karel Driesen for letting us use his 
class hierarchies benchmark for this work. This work was partially 
supported by NSF grants CCF-0702765, CCF-1043084, and CCF-1150055.

\bibliographystyle{abbrvnat}
\bibliography{mlpatmat}
\end{document}
